1. Technical Field of the Invention
This invention relates to a peak data extracting device and a rotary motion recurrence formula computing device which are used in picture processing devices using, e.g., Hough transform.
2. Related Background Art
In controlling an unmanned movable robot or an automatic movable vehicle, for example, the pictures of the lines marking off a lane, and those of the center line and the shoulder lines of a road have to be taken by a camera to be subjected to picture processing. FIG. 1(a) and (b) are views explaining recognition of a road by means of a picture. FIG. 1(a) shows a picture of a road taken by a camera. FIG. 1(b) is a view in which the picture elements in FIG. 1(a) having higher brightness (or higher brightness change ratios) are shown in black points.
As shown in FIG. 1(a), in a camera picture 1 a road 3 is extended at infinity toward a horizontal line 2. Shoulder lines 4 are on both sides of the road 3. A center line 5 is at the center of the rod 5. The shoulder lines 4 and the center line 5, of the road 3 have higher brightnesses than the other parts of the road 3 and are shown in continuous dots 4', 5' as shown in FIG. 1(b). Based on this camera picture 1, in order to recognize the direction and curves of the road 3, approximate straight lines L.sub.1, L.sub.2, L.sub.3 interconnecting the dots 4' in FIG. 1(b) are recognized.
As a method for giving the approximate straight lines L, the method called Hough transform is conventionally known (e.g., specification of U.S. Pat. No. 3,069,654). Assuming that a point P (x.sub.p, y.sub.p) to be processed is present on an original picture drawn by the x-y coordinate system as shown in FIG. 2(a), an infinite number of straight lines l (l.sub.a, l.sub.b, . . . ) can be drawn. Straight lines passing the origin O (0,0) and orthogonal to the respective straight lines l.sub.a, l.sub.b, . . . can be also depicted. When a length of the straight lines l passing the origin O (0,0) to the straight lines l (l.sub.a, l.sub.b, . . . ) is represented by .rho.(.rho..sub.a, .rho..sub.b, . . . ) and an angle these straight lines form to the x axis is represented by .theta.(.theta..sub.a, .theta..sub.b, . . . ) the .rho. and .theta. of the straight lines passing the origin O (0,0) are given in the sine curve of FIG. 2(b), i.e., the Hough curve. The length .rho..sub.max between the origin O (0,0) and the point to be processed P (x.sub.p, y.sub.p) is the longest of the straight lines passing the point to be processed P (x.sub.p, y.sub.p). The length is given by EQU .rho..sub.max =(x.sub.p.sup.2 +y.sub.p.sup.2).sup.1/2
and when .theta.=0, .rho..sub.0 =x.sub.p.
Next, Hough transform of FIG. 2(a) and (b) will be applied to three points P.sub.1 .about.P.sub.3 on a straight line L shown in FIG. 3(a). The sine curve (Hough curve) in the dot line in FIG. 3(b) is given with respect to the point P.sub.1. The sine curve (Hough curve) with respect to the point P.sub.2 is in the one dot line in FIG. 3(b), and that with respect to the point P.sub.3 is in the two dot line in FIG. 3(b). The peaks (.rho..sub.1, .theta..sub.1), (.rho..sub.2, .theta..sub.2) and (.rho..sub.3, .theta..sub.3) of the respective sine curves of FIG. 3(b) correspond to the lengths .rho..sub.1 .about..rho..sub.3 between the origin O (0,0) and the respective points P.sub.1, P.sub.2 and P.sub.3 in FIG. 3(a), and the angles .theta..sub.1 .about..theta..sub.3 the respective straight lines passing the origin O form to the X axis.
In FIG. 3(b), the point of intersection of the three Hough curves (sine curves) has coordinates (.rho..sub.t, .theta..sub.t) which are equal to .rho..sub.t, .theta..sub.t of a straight line passing the origin O (0,0) and orthogonal to the straight line L. Thus by obtaining a point of intersection of such sine curves, an approximate straight line of the curves interconnecting the dots (dark points) in the x-y rectangular coordinate system of an original picture can be obtained (in FIGS. 3(a) and (b), however, the curves and the approximate straight line are in agreement).
This will be explained with reference to FIGS. 4(a) and (b). It is assumed that a number of dots (points to be processed) to be Hough transformed are on a curve in the x-y coordinate plane (original picture plane) in FIG. 4(a). In FIG. 4(a) three approximate straight lines L.sub.1, L.sub.2, L.sub.3 interconnecting the dots can be depicted. When sine curves (Hough transform) are given with respect to all these dots, as in FIG. 2(b), three points of intersection of the sine curves are obtained. The three points of intersection have coordinates (.rho..sub.t1, .theta..sub.t1), (.rho..sub.t2, .theta..sub.t2), (.rho..sub.t3, .theta..sub.t3) in FIG. 4(a). When the occurrence of the point of intersection H is expressed by the .rho., .theta., H coordinate system, FIG. 4(b) is given. Accordingly, the approximate straight lines L.sub.1 .about.L.sub.3 of FIG. 1(b) corresponding to the shoulder lines 4 of the road 3 can be given in values of .rho. and .theta. at a peak of H (the occurrence of the point of intersection).
But, when a very large number of points to be processed are present in an original picture, a very large number of Hough curves are given corresponding to the points, and resultantly a very large number of intersecting points of the Hough curves are given. Since the intersecting points overlap in the .rho., .theta. plane, occurrence H of the points of intersection distributes, e.g., in FIG. 5. In FIG. 5, the first highest peak (P.sub.1) indicates a maximum occurrence, and the occurrence H decreased in the order of peaks P.sub.3, P.sub.4 and P.sub.2. But the second and third highest peaks P.sub.3 and P.sub.4 are near the first highest peak P.sub.1 and thus is reduced to noise components in the picture processing. To the contrary, the peak P.sub.2 has a lower peak value than the peaks P.sub.3 and P.sub.4, but in the picture processing the peak P.sub.2 is a peak to be detected desirably next to the peak P.sub.1. Unless the peak P.sub.2 can be detected, the picture processing becomes very difficult as will be explained below.
As means for removing such noise components, it is considered to use software of a computer. But this makes the system large and needs a longer processing time.
A first object of this invention is to provide a peak data extracting device which can extract peak data with noise components removed, by a simple system and at high speed.
On the other hand, for the Hough transform mentioned above, there have been proposed processes which compute rotary motion recurrence formulas. In these processes, with reference to FIG. 6, a point P.sub.i+1 (x.sub.i+1, y.sub.i+1) can be computed, based on a point P.sub.i (x.sub.i, y.sub.i) using Formula 5, 6 which is derived as follows. That is, in a rectangular x-y coordinate system, the point P.sub.i+1 (x.sub.i+1, y.sub.i+1) to which the point P.sub.i (x.sub.i, y.sub.i) spaced by .rho. from the origin O(0,0) is rotated by .epsilon. (rad) with the origin centered is given as follows. That is, when EQU x.sub.i =.rho..multidot.cos .theta. (1) EQU y.sub.i =.rho..multidot.sin .theta. (2) EQU x.sub.i+1 =.rho..multidot.cos (.theta.+.epsilon.) (3) EQU y.sub.i+1 =.rho..multidot.sin (.theta.+.epsilon.) (4)
Then Formulas 3 and 4 are expanded by the addition thereon, and the resulting equations are substituted by Formulas 3 and 4 to obtain the Formula 5, 6 EQU x.sub.i+1 =cos .epsilon..multidot.x.sub.i -sin .epsilon..multidot.y.sub.i ( 5) EQU y.sub.i+1 =sin .epsilon..multidot.x.sub.i +cos .epsilon..multidot.y.sub.i ( 6)
But this computation includes the trigonometric function, which consequently not only makes it inconvenient to prepare the hardware but also makes the computation unsuitable for high speed processing. As a countermeasure to these disadvantages, Taylor's expansion leads the sine .epsilon. and the cos .epsilon. to EQU sin .epsilon.=.epsilon.-.epsilon..sup.3 /3!+.epsilon..sup.5 /5!-.epsilon..sup.7 /7!+ (7) EQU cos .epsilon.=1-.epsilon..sup.2 /2!+.epsilon..sup.4 /4!-.epsilon..sup.6 /6!+(8)
Then the first order approximation reduces Formulas 7 and 8 to sin .epsilon.=.epsilon. and cos .epsilon.=1, and the following rotary motion recurrence formula EQU x.sub.i+1 =x.sub.i -.epsilon.y.sub.i ( 9) EQU y.sub.i+1 =.epsilon.x.sub.i +y.sub.i ( 10)
is given. According to the rotary motion recurrence formula 9, 10, the rotary motion becomes spiral, and the recurrence formula 9, 10 is not practically used. For the prevention of spiralling of the rotary motion due to errors occurring in rotation, the following rotary motion recurrence formula EQU x.sub.i+1 =x.sub.i -.epsilon.y.sub.i ( 11) EQU y.sub.i+1 =.epsilon.x.sub.i+1 +y.sub.i ( 12)
is used in circle generating DDA computations. The recurrence formula 11, 12 is computed by the hardware exemplified in FIG. 7. The formula 11, 12 enables a rotary motion to be approximated by comparatively simple hardware.
Although the conventional computing device described above enables the rotary motion recurrence formulas to be computed at high speed, a disadvantage with the devices is that computation errors are so large that the devices are not suitable for computations requiring high precision. That is, in drawing a semicircle as indicated by the solid line in FIG. 8(b), an error becomes larger as a computation goes on the rotary motion recurrence formulas, and an error d generated when a point P.sub.0 (x.sub.0, y.sub.0) is rotated by .pi. (rad) becomes unnegligible. Here, when a relative error d' (%) is defined by EQU d'=(d/R).times.100 (%)
(where R is a radius of a circle), the hardware for the conventional first order approximation as shown in FIG. 8(a) and that for the conventional DDA as shown in FIG. 7 generate the relative errors d' stated in FIG. 9.
The hardware involving such errors cannot be used for, e.g., Hough transforms. That is, in a case where a relative error with respect to a diameter of a circle is about .+-.0.4% (the quantitized error for the case, for example, where .rho.(a distance from the origin to a line segment) is divided into 128 sections to Hough transform is within .+-.0.4%), no practical troubles take place, but for such relative error, the rotation angle .epsilon. has to be made very small.
A second object of this invention is to provide a device for computing a rotary motion recurrence formula whose hardware structure is simple, which is suitable for high speed computation and allows large rotation angles to be set while making errors minimum.